本文的选题依据来自 https://cspiration.com/leetcodeClassification 中的划分,下面的序号以 Leetcode 英文版为准
⭐51.N-Queens
- 经典的 N 皇后问题,它可以通过回溯法解决,本题主要注意的点是验证冲突,所以我在 valid 中写了三个方向(上方,左上,右上)的校验,然后就是对数据进行遍历,注意加入数据后进行痕迹消除
52.N-Queens II
- 对 N 皇后问题的解法进行统计,直接对上题中的结果进行统计即可
⭐53.Maximum Subarray
- 最大子序列问题是典型的 DP 问题,将 dp 数组填满即可,对于 dp[i-1]小于 0 的情况,说明前面的子序列之和小于 0,所以进行舍弃;否则就用当前数值加上之前子序列之和
54.Spiral Matrix
- 没有太多技巧,每个方向判断
55.Jump Game
- 该题主要是理解 i 和 max 的意思,i 代表当前所在下标,而 max 代表之前的点能到达的最远位置,如果 i>max 就代表,当前坐标已经大于之前能到达的最远距离了,所以返回 false,否则更新 max 值
56.Merge Intervals
- 使用扫描线算法先对数组进行排序,排序规则是 start 小的在前,之后就是顺序比较两个相邻元素的大小,取 start 的最小和 end 的最大值
57.Insert Interval
- 同样使用扫描线算法进行合并
58.Length of Last Word
- 没什么好说的
59.Spiral Matrix II
- 没有太多技巧,每个方向判断
⭐60.Permutation Sequence
- 该题主要是要理解全排列的组合方式,以 1234 为例,它总共有 4!=24 种排列。当第一位决定后,第二位共有 3!=6 种排列;当第二位决定后,第三位共有 2!=2 种排列;当第三位决定后,第四位只有 1 种选择了,以 n=4,k=17 为例,最高位可以取 1234 中的一个,每个数字出现 3!次(因为当最高位决定了,后面三位可以任意排列,所以最高位会出现 3!次),当 k=16(为编程方便,程序以 0 为开始),第一位的下标是 16/6=2,因为每个可以出现 6 次,那么除以 6 之后自然能够得出当前应该出现的数字下标是几,此时下标为 2 的数字 3 被选出。此时 3 被删除,只剩下 124
- 从 124 中取一个,k=16,在此轮中的 k=16%(3!)=4,这里取余是因为这个位置是第三组(k/6=2)的第五个(k%6=4)数字,剩下的处理和上面一样,每个数字出现的 2!=2 次,第二数字的下标为 4/2=2,故 4 被取出,并被移除
- 从 12 中取一个,k=4,在此论中的 k=4%(2!)=0,而剩下数字出现 1!=1 次,所以第三个数字下标为 0/1=0,在 12 中就是 1 被取出,只剩下 2,故结果是 3412